import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Offer_33 {
    /**
     * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。
     * <p>
     * 参考以下这颗二叉搜索树：
     * <p>
     * 5
     * / \
     * 2   6
     * / \
     * 1   3
     * 示例 1：
     * <p>
     * 输入: [1,6,3,2,5]
     * 输出: false
     * 示例 2：
     * <p>
     * 输入: [1,3,2,6,5]
     * 输出: true
     */

    public  boolean verifyPostorder(int[] postorder) {
        if (postorder == null || postorder.length <= 0) {
            return true;
        }

        return verifyPostorder(postorder, 0, postorder.length - 1);
    }

    private  boolean verifyPostorder(int[] postorder, int left, int right) {
        if (left >= right) {
            return true;
        }
        int root = postorder[right];
        int i = left;
        for (; i < right; i++) {
            if(postorder[i]>root){
                break;
            }
        }
            for (int j = i; j < right; j++) {
                if(postorder[j]<root){
                    return false;
                }
            }

        boolean leftIsBST = true;
        leftIsBST = verifyPostorder(postorder,left,i-1);

        boolean rightIsBST = true;
        rightIsBST = verifyPostorder(postorder,i,right-1);

        return leftIsBST&&rightIsBST;
    }

    public static void main(String[] args) {
        int[] postorder = new int[]{1,2,5,10,6,9,4,3};
//        System.out.println(verifyPostorder(postorder));

        LinkedList<Integer> path = new LinkedList<>();
        path.add(1);
        path.add(2);



        System.out.println(path.removeLast());
    }
}
